package com.aqie.medium.reservoirSampling;

import com.aqie.easy.structure.ListNode;

import java.util.Random;

/**
 * 382 链表随机节点
 */
public class LinkedListRandomNode {
    /**
     * 1, 137ms
     */
    private ListNode node;
    public LinkedListRandomNode(ListNode head) {
        node = head;
    }

    /** Returns a random node's value. */
    public int getRandom() {
        ListNode res = node;
        ListNode cur = node.next;
        int i = 2;
        //从第二个节点开始,每次循环替换res的概率都是1/i
        while(cur != null){
            Random random = new Random();
            int ran = random.nextInt(i);
            if(ran == 0){
                res = cur;
            }
            cur = cur.next;
            i++;
        }
        return res.val;
    }
}
